\chapter{Contributions} 
As discussed in the previous chapter, various techniques have been proposed
to solve the Single-mode Trace Signal Selection (SMTS) problem. The major
concern is to improve the solution quality while maintaining a high
runtime-scalability with the growing size of the designs. Simulation-based
algorithms can measure the State Restoration Ratio (SRR) accurately when
selecting the trace signals but they show poor runtime-scalability compared
to metric-based algorithms. In contrast, metric-based algorithms have the
advantage of fast runtime. But they usually lead to worse solution quality
than simulation-based algorithms due to the inaccuracy of the metrics
defined to estimate the SRR. In this dissertation, we first propose a
``hybrid'' trace signal selection algorithm which utilizes the right blend
of simulation and quickly-measured metrics that we propose to solve the
SMTS problem.

Identifying control signals is currently done manually however in modern
designs control signals may be inserted automatically by the CAD tools
which makes manual identification not to be straight-forward. Therefore, we
next present a procedure for automatic identification of control signals in
a design. We then identify the challenge of SMTS in the presence of control
signals which make a circuit operate in different modes. We show that
considering only a single-mode during the trace signal selection causes
poor restoration quality in the other modes. Using our procedure for
identifying the control signals, we next introduce the Multi-mode Trace
Signal Selection (MMTS) problem.  \newpage

\section{A Hybrid Algorithm for Fast and Accurate Single-mode Trace
\newline Signal Selection} 
Given our overview of the advantages and disadvantages of various existing
simulation-based and metric-based trace signal selection algorithms, in
Chapter 4, we first present a new {\it hybrid} trace signal selection
algorithm which combines simulation and a new set of proposed metrics to
select the signals for tracing quickly while keeping high solution quality
in terms of SRR. The contributions of this portion are as follows.

\begin{itemize}
\item A new set of metrics are proposed to quickly, yet accurately identify
the top candidates for tracing at each step of our trace signal selection
algorithm. Next, only a few number of simulations are used to accurately
select the next trace signal among these top candidates.
\item These metrics include an \emph{impact weight} of each state element
for relative comparison which further depends on a proposed \emph{demand}
metric. The demand metric reflects the remaining restoration needed by a
state element to be restored from a candidate state element for tracing,
after taking into account partial restoration from the already-selected
trace signals.
\item Updating the impact weight and demand metrics at each step is also
done quickly and involves a small number of simulations over all the
not-traced state elements.
\end{itemize}

In our experimental results, we first use a setup similar to the previous
works which experiments with trace buffers of different widths on the
ISCAS'89 benchmarks \cite{ISCAS89}. We also take into account the impact of
control signals in our algorithm when conducting our experiments but only
consider a single-mode of operation at each experiment for the SMTS
problem. We demonstrate in the simulation results that the solution quality
of our algorithm in terms of the measured SRR is comparable or better than
a simulation-based approach which has the best reported solution quality
among the existing algorithms. At the same time, our algorithm is
significantly faster than simulation-based techniques and has a runtime
comparable to metric-based techniques which have the fastest runtime among
the existing algorithms. We also show the breakdown of different metrics
with their impacts on the solution quality, to give a better view of how
the metrics are defined and combined. The metrics defined for the selection
process are then extended to account for large benchmarks and we also
report simulation results showing that our algorithm is scalable when
experimenting on larger benchmarks from the IWLS'05 \cite{IWLS05} and
ISPD'12 \cite{ISPD12} benchmark suites.

\section{Automated Identification of Control Signals} Control signals are a
subset of the primary inputs which typically have low switching activity and can
influence a large portion of a circuit. The operation conditions when
control signals take different values are referred as different ``operation
modes'' (or ``working modes''). ``Reset'' signals are typical control
signals that can greatly affect the operation of a circuit when they are
activated. Besides the reset signals, examples of control signals include
signals for mode selection, communication between two design blocks, power
gating and clock gating, encryption, etc. \cite{JTG13}. Some of these
control signals may also be introduced by the CAD tools for example based
on automated strategies for controlling sleep/wake-up in power-gated
designs (e.g., \cite{LeeSC12}). Control signals can have great impact on
the quality of trace signal selection, thus they need to be identified
prior to the trace signal selection process.

It is no longer possible to identify the control signals manually. First,
this is because the number of cells as well as primary inputs in a design
increases as technology scales. Second, as modern designs become more complex, it is
impossible to accurately evaluate the impact of each signal using
manual techniques, especially when the designs are synthesized into
gate-level netlist and control signals are introduced by the CAD tools
\cite{JTG13, LeeSC12}.  Therefore, automated identification of the control
signals is necessary.

In this dissertation, we assume only gate-level netlist is available when
identifying the control signals. This is consistent with the common
situation that validation engineers only have access to the netlist, with
limited information about the primary inputs regarding their usage (as
data, address, or control inputs) \cite{JTG13, KoDis}. Some of the control
inputs can impact a large portion of a circuit (e.g., the reset signals),
while others can only influence a small portion (e.g., an enable signal for
a small design block with few gates). In this work, we aim to identify the
first set which have a high impact on the design. Specifically, in Chapter
5, we propose an automated control signal identification procedure which
combines fast X-Simulation
%(which was described in Section \ref{sec:sr}) 
with limited knowledge of the each primary input (such as if an input is
used as data, address, or control). We use simulation
to quickly narrow down the scope of search among the primary inputs based
on the input type. 

In our experimental results, we apply the identification procedure to
benchmarks from ISCAS'89 \cite{ISCAS89} to compare with an existing work on
control signal identification \cite{KoDis} which was applied to the same
benchmarks. Our procedure can identify exactly the same set of control
signals which were manually identified in \cite{KoDis}. We also apply it to
large benchmarks from IWLS'05 \cite{IWLS05} and ISPD'12 \cite{ISPD12} gate
sizing contest to show more details about how our procedure works. Overall,
our procedure shows good runtime-scalability so it is able to identify the
control signals for large benchmarks within tens of seconds. It can also
correctly identify the control signals compared with the existing approach
\cite{KoDis}.

\section{Multi-mode Trace Signal Selection in the Presence of Control
\newline Signals} To acknowledge the impact of control signals on trace
signal selection, previous works have considered generating \emph{separate}
solutions for each operation mode \cite{BasuM13, ChatterjeeMB11, KoN09,
LiD13,LiD14TCAD, LiuX12, ShojaeiD10}; this means the control signals are kept
constant during each trace signal selection process. However as we show in
this dissertation, by selecting trace signals optimized for a
single operation mode, the SRR of the remaining modes can be significantly 
degraded for that same solution. This issue may
significantly bring down the value of trace buffers, if bug analysis at the
post-silicon stage needs to be conducted using trace signals selected for a 
different operation mode than the one where the bug is
observed at. Moreover, while it is possible to find different sets of trace
signals for each operation mode, and feed them all to an interconnect
network \cite{LiuX-ITC12, PrabhakarSH11} which selects only one set for
tracing at each time, the overhead of such a network (including the routing
overhead to feed in various signals to the network) may significantly
increase with increase in the number of operation modes.

Using our automated control signal identification process, we next propose
a new definition of the trace signal selection problem when considering
multiple operation modes. We refer to it as the Multi-mode Trace Signal
Selection (MMTS) problem. MMTS aims to maximize an objective corresponding
to the state restoration ratio over all the operation modes. Our
contributions are summarized below.

\begin{itemize}
\item[1.] We propose a procedure to reduce the number of modes by merging
the modes with ``similar'' restoration maps. This is done by introducing a
metric to measure the extent of similarity of two operation modes.
\item[2.] We introduce the Multi-mode Trace Signal Selection (MMTS) problem
by first extending the definition of SRR to consider the modes of
operation, based on which we then give the definition of the MMTS problem.
\item[3.] We propose a way to generate an upper bound on the solution
quality to provide a point of reference for comparison among different
algorithms.
\item[4.] We propose a procedure based on perturbing an initial
single-mode-optimized solution, selected from a suitable ``start'' mode to
improve the restorability over all the modes. Our algorithm has a
non-greedy nature and at each iteration tries to improve the previous
solution with a gradually-increasing perturbation radius.
\end{itemize}

In our simulation results, we use large-sized designs from IWLS'05
\cite{IWLS05} and ISPD'12 \cite{ISPD12} gate sizing contest benchmarks with
up to 150K gates. We measure the quality of our algorithm with respect to a
point of reference which provides an upper bound, as well as four other
alternative strategies. We also verify in our experiments that different
steps in our algorithm are all necessary which contribute to a high quality final solution. Moreover, we show that the
mode merging process can help reduce the runtime of the algorithm by only
considering one mode in each merged group, with little degradation in
solution quality.